package code301_400;

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;

public class Code347 {




    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i:nums){
            if (map.containsKey(i)){
                map.put(i,map.get(i)+1);
            }else {
                map.put(i,1);
            }
        }


        Queue<Freq> queue = new PriorityQueue<>();
        for (Map.Entry<Integer,Integer> entry : map.entrySet()){
            if (queue.size()<k){
                queue.add(new Freq(entry.getKey(),entry.getValue()));
            }else {
                Freq freq = queue.peek();
                if(entry.getValue()<freq.times){
                    continue;
                }else {
                    queue.poll();
                    queue.add(new Freq(entry.getKey(),entry.getValue()));
                }
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i <  k; i++) {
            ret[i] = queue.poll().key;

        }

        return ret;
    }



}

class Freq implements Comparable<Freq>{

    int key;
    int times;

    public Freq(int key, int times) {
        this.key = key;
        this.times = times;
    }


    @Override
    public int compareTo(Freq o) {
        return this.times-o.times;
    }
}